#include "main/utils.h"
using namespace std;

bool isMapAllZero(const map<char, int> &help_map) {
  for (auto ele : help_map) {
    if (ele.second != 0) {
      return false;
    }
  }
  return true;
}

bool isAnagram(const string &s1, const string &s2) {
  if (s2.length() < s1.length()) {
    return false;
  }
  map<char, int> help_map;
  for (int i = 0; i < s1.size(); ++i) {
    if (help_map.find(s1[i]) == help_map.end()) {
      help_map[s1[i]] = 1;
    } else {
      ++help_map[s1[i]];
    }
    if (help_map.find(s2[i]) == help_map.end()) {
      help_map[s2[i]] = -1;
    } else {
      --help_map[s2[i]];
    }
  }

  int begin = 0;
  int end = s1.size() - 1;
  while (end < s2.size()) {
    if (isMapAllZero(help_map)) {
      return true;
    }
    if (help_map.find(s2[++end]) == help_map.end()) {
      help_map[s2[end]] = -1;
    } else {
      --help_map[s2[end]];
    }
    ++help_map[s2[begin++]];
  }
  return false;
}

int main() {
  string s1 = "ac";
  string s2 = "dgcaf";
  bool ret = isAnagram(s1, s2);
  cout << ret << endl;

  cout << isAnagram("ac", "dgcaf") << " " << isAnagram("ac", "abcde") << " " << isAnagram("abc", "ghoetheabc") << endl;

  return 0;
}
